Wiercenia [A]

Limit pamięci: 128 MB

Bajtazar kieruje ekipą poszukującą złóż ropy. Wykonał dwa odwierty: w punkcie natrafił na ropę, zaś w punkcie okazało się, że ropy nie ma. Wiadomo, że złoże ropy zajmuje pewien spójny fragment odcinka o jednym końcu w punkcie . Bajtazar musi teraz ustalić, jak daleko, wzdłuż odcinka łączącego punkty i , sięga złoże ropy. Nie jest to jednak takie proste, gdyż w jednych miejscach wierci się szybciej, a w innych wolniej. Ponadto ekipa Bajtazara jest niewielka, dlatego mogą wykonywać tylko jeden odwiert naraz. Szef Bajtazara domaga się od niego, żeby określił, do kiedy ustali granicę złoża ropy.

Bajtazar poprosił Cię o pomoc. Podzielił on odcinek łączący punkty i na równych odcinków. Jeśli przyjmiemy, że punkt ma współrzędną 0, a punkt współrzędną , to między nimi mamy punktów o współrzędnych . Wystarczy, że zostanie zlokalizowany najdalszy z tych punktów, patrząc od punktu , w którym występuje ropa. Bajtazar podał Ci czasy potrzebne na wykonanie odwiertów w tych punktach - wynoszą one, odpowiednio, . Musisz ustalić taki plan wierceń, aby czas potrzebny na ustalenie, dokąd sięga złoże ropy, był w pesymistycznym przypadku jak najkrótszy.

Wejście

W pierwszym wierszu standardowego wejścia zapisana jest jedna dodatnia liczba całkowita (). W drugim wierszu zapisanych jest dodatnich liczb całkowitych , pooddzielanych pojedynczymi odstępami ().

Wyjście

Twój program powinien wypisać na standardowe wyjście jedną liczbę całkowitą - najkrótszy czas, jaki Bajtazar musi (zakładając najbardziej pesymistyczny scenariusz) przeznaczyć na odwierty w poszukiwaniu ropy, by mieć pewność, że uda mu się ustalić zasięg złoża.

Przykład

Dla danych wejściowych:

4
8 24 12 6

poprawną odpowiedzią jest:

42

Wyjaśnienie do przykładu. Załóżmy, że Bajtazar dokona pierwszego odwiertu w punkcie , co zajmie mu czas . Może się wówczas okazać, że znajdzie tam ropę i będzie zmuszony sprawdzić, jak daleko na prawo sięga złoże. Potrzebne mu będą jeszcze dwa odwierty, które w najgorszym razie potrwają . Zatem w tym wypadku na całą pracę Bajtazar będzie musiał poświęcić jednostki czasu.

Okazuje się, że lepiej zacząć od punktu numer . Jeśli nie będzie tam ropy, to wystarczy sprawdzić punkt . Jednak w pesymistycznym przypadku Bajtazar będzie zmuszony zrobić kolejne dwa odwierty w punktach oraz i zakończyć pracę w łącznym czasie .

Autor zadania: Marcin Kubica.